FIG. 1 is a drawing that will be used in the description of an example of bandwidth allocation in communication between switching office equipment 10 and subscriber terminals (personal computers, for example) via subscriber devices (network units) 11, . . . , 14. When the bandwidth available between the switching office equipment 10 and the subscriber devices 11, . . . , 14 is limited, as shown in FIG. 1, the individual subscriber devices 11, . . . , 14 declare parameters, such as communication bandwidths, to the switching office equipment 10 (step ST1). The switching office equipment 10 accepts the declarations from the subscriber devices 11, . . . , 14 if the declarations are acceptable, and rejects the declarations if they are unacceptable (step ST2). The subscriber devices 11, . . . , 14 carry out communication in the bandwidth permitted by the switching office equipment 10, and if communication is carried out in non-permitted (non-compliant) bandwidth, the information is discarded (step ST3). In order to prevent the discarding of information due to such violations, there is also a method in which, before transmitting, the subscriber devices 11, . . . , 14 again issue a request to transmit to the switching office equipment 10, receive permission to transmit together with transmission timing, channel bandwidth, and other information from the switching office equipment 10, and carry out transmission based on the information. The present invention mainly relates to communication in the allocated bandwidth, which is the operation in step ST3 in FIG. 1, but the invention is also applicable to the bandwidth request process in step ST1.
The optical access network illustrated in FIG. 2 is a more specific example of the configuration shown in FIG. 1. The optical access network shown in FIG. 2 includes an optical line terminal (OLT) 20 as switching office equipment and optical network units (ONUs) 21, . . . , 24, a coupler (splitter) 25, optical fibers 26a, . . . , 26d connecting the ONUs 21, . . . , 24 to the coupler 25, and a single optical fiber 27 connecting the OLT 20 to the coupler 25. Each ONU must transmit optical signals at timings such that its upstream signals do not collide with upstream signals from the other ONUs in the coupler 25. The OLT 20 notifies the ONUs 21, . . . , 24 of the transmission timings.
FIG. 3 illustrates a wireless code division multiple access (CDMA) configuration, which is another specific example of the configuration shown in FIG. 1. In the wireless communication illustrated in FIG. 3, a base station (switching office equipment) 30 communicates with subscriber terminals 31, . . . , 34 by using a shared air transmission medium and radio waves. In the CDMA communication system, a frequency band is divided into code channels (for example, CH1, . . . , CH4) and the channels are divided into timeslots. Optical access systems using optical CDMA technology work in the same way.
In communication systems such as the ones shown in FIGS. 1 to 3, a mechanism for allocating bandwidth to subscriber devices is essential. The dual leaky bucket algorithm disclosed in, for example, non-patent document 1 can be used to implement this mechanism. A traffic management method for ATM (asynchronous transfer mode) networks using a UPC (usage parameter control) scheme is disclosed in, for example, non-patent document 2.
FIG. 4 illustrates a UPC scheme using the leaky bucket algorithm. This scheme describes bandwidth control by use of a bandwidth control model in which information (traffic, packets, or tokens) is likened to ‘water’ and a queue used for holding information is likened to a ‘leaky bucket’. This scheme uses two ‘leaky buckets’ (queues) 41, 42 and functions for reading information therefrom, as shown in FIG. 4, for each input line. Input ‘water’ 43 is input to a first-stage ‘leaky bucket’ 41. The input ‘water’ is information that a terminal wants to transmit; the amount of information may increase or decrease, or may become zero in some cases. A fixed amount of ‘water’ flows out of the first-stage ‘leaky bucket’ 41 per unit time (that is, a fixed amount of information per unit time is read from the queue). The declared peak rate Tp corresponds to the size of the ‘hole’ 41a in the first-stage ‘leaky bucket’ 41 (the amount of information read out per unit time). The volume 41b of the first-stage ‘leaky bucket’ defines the permissible amount of ‘water’ that violates (exceeds) the peak rate. If input of ‘water’ in violation of the peak rate persists over a long time, the ‘water’ overflows the first-stage ‘leaky bucket’ 41 and is discarded.
The size of the ‘hole’ 42a in the second-stage ‘leaky bucket’ 42 (the amount of information read out per unit time) corresponds to an average bandwidth size (average rate). The volume 42b of the second-stage ‘leaky bucket’ defines the permissible amount of ‘water’ that violates (exceeds) the average flow rate Ta of the output from the ‘hole’ 42a. That is, the volume of the second-stage ‘leaky bucket’ 42 defines the permissible range of temporal sway of the inflowing ‘water’ (arriving packets). If the amount of information Tpe that arrives during a certain time period Pe exceeds Ta×Pe (that is, Tpe>Ta×Pe), the violating traffic overflows the second-stage ‘leaky bucket’ 42 and is discarded.
The mechanism illustrated in FIG. 4 may be implemented in each subscriber's subscriber device (network unit) and configured so that packets (traffic) are input as ‘water’. Alternatively, as described in the non-patent documents 1 and 2 mentioned above, as many mechanisms like the one shown in FIG. 4 as the number of subscribers may be implemented in the switching office equipment, and the subscriber devices may be configured so as to control their user data transmission timing and transmission time responsive to control data from the switching office equipment. In this case, the ‘leaky buckets’ receive declarations of communication bandwidth from the subscribers and receive tokens, which are information about traffic in the queues implemented in the subscriber terminals; the output from the ‘leaky buckets’ is transmitted to the subscriber devices (ONUs) as transmission permission signals; and the permitted amount of traffic is output from the subscriber devices.    Non-patent document 1: Performance Limitation of Leaky Bucket Algorithm for Usage Parameter Control and Bandwidth Allocation Methods by Naoaki Yamanaka et al., pp. 82-86, IEICE TRANS. COMMUN., Vol. E75-B, No. 2, February 1992    Non-patent document 2: Kakuteiteki UPC ni yoru ATM mo torahikku manejimento hoshiki (Traffic Management Method for ATM Network Using Precise UPC Scheme) by Naoaki Yamanaka et al., pp. 253-263, B-1, Vol. J76-B-I, No. 3, March 1993    Patent document 1: Japanese Patent Application Publication No. H05-153154
There are two major problems with the above communication system for controlling traffic volume based on an average bandwidth and maximum bandwidth.
The first problem is that such a communication system may lead to waste of bandwidth (unused bandwidth). With the method shown in FIG. 4, if the inflow of ‘water’ exceeding the average bandwidth to the second-stage ‘leaky bucket’ persists for a prolonged time, ‘water’ overflows from the second-stage ‘leaky bucket’ and is discarded. On the other hand, if inflow of a small amount of ‘water’ to the second-stage ‘leaky bucket’ persists for a prolonged time, it will only be possible to transmit data at a much lower rate than the declared average value.
For example, under a simultaneous contract for average and peak rates, if a user who signed up for an average 1-Mbit/sec transfer rate and 2-Mbit/sec peak (maximum) rate performed communication for only one minute at only 64 kbits/sec yesterday but wants to communicate at 1.9 Mbit/sec for twenty hours today, the subscriber's request will not be accepted by most contracts and communication systems, which generally allow the peak rate for only several tens of seconds at most. There is some merit to the idea that it is only natural to discard traffic sent in excess of the declared value, and that it is the subscriber's fault if he or she did not send as much traffic as he or she could have the previous day.
There is also some merit, however, to the idea that if bandwidth is being left unused by other subscribers, a subscriber who wants to use that bandwidth should be allowed to do so. The available bit rate (ABR) scheme is a network usage scheme based on this idea. In this scheme, a subscriber device declares a minimum guaranteed bandwidth and the maximum accommodatable bandwidth when making a bandwidth declaration. The art for implementing this scheme includes the art disclosed in Patent Document 1. This art uses the terms ‘minimum limit bandwidth’ and the ‘maximum limit bandwidth’, but these terms may be considered conceptually the same, substantially, as the terms ‘minimum guaranteed bandwidth’ and ‘maximum accommodatable bandwidth’ in the present invention. When a subscriber requests communication in a bandwidth beyond the minimum guaranteed bandwidth, the art described in Patent Document 1 decides whether any bandwidth remains after subtraction of the minimum guaranteed bandwidth from the entire bandwidth, and if so, whether the bandwidth may be allocated or not, and sets the ATM switch based on the decision result, but the method of carrying out the calculations for allocating bandwidth to carry out this operation is not described.
The second problem will now be described. The above communication system assumes that the subscriber device has functions capable of transmitting signals arbitrarily in all channels and all timeslots in the upstream bandwidth. That is, it is assumed that a CDMA communication terminal, for example, has hardware and software capable of generating all types of sequences receivable by the switching office equipment. An implementation that enables transmission on all channels, however, may raise the cost of manufacturing the device. With a cost-cutting configuration that reduces the number of available channels and timeslots, however, there will be constraints on allocatable channels and timeslots, causing waste of bandwidth, and when a terminal has much signal traffic to transmit and other terminals with which it shares bandwidth also have much signal traffic to transmit, there is a strong possibility that the transmittable traffic will be constrained.
The present invention addresses the above problems of the prior art, with the object of providing a dynamic bandwidth allocation method and a dynamic bandwidth allocation device capable of dynamic bandwidth allocation which guarantees communication in the minimum guaranteed bandwidth declared by each subscriber and enables communication within the maximum accommodatable bandwidth declared by each subscriber. Another object of the invention is to provide a dynamic bandwidth allocation method and a dynamic bandwidth allocation device that can implement dynamic bandwidth allocation at a reduced device manufacturing cost.